package 剑指offer;

import java.util.Arrays;

public class p12矩阵种的路径 {
//    public static void main(String[] args) {
//        int[][] a={{1,2},{3,4}};
//        System.out.println(a.length);
//        test(a);
//        System.out.println(Arrays.deepToString(a));
//    }
//
//    private static void test(int[][] a) {
//        a[0][0]=99;
//    }


    // 深度优先搜索DFS+剪枝策略！！
    public boolean exist(char[][] board, String word) {
        char[] words=word.toCharArray();

        for (int i = 0; i <board.length; i++) {
            for (int j = 0; j <board[0].length; j++) {
                //从 第一个元素开始，递归检查当前字符 是否符合要求
                if (dfs(board,words,i,j,0)) {
                    //如果 找到该字符对应的 words，则程序结束返回 true
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, char[] words, int i, int j, int k) {
        if (i > board.length || i < 0 ||
            j>board[0].length || j < 0 ||
            board[i][j] != words[k]) {
            //行越界
            //列越界
            //矩阵中的当前字符 ！= 单词中的字符
            return false;
        }

        // board[i][j] == words[k]，且 已经是 words中的最后一个字符，则路径查找完毕，返回true
        if (k==words.length-1) {
            return true;
        }

        //board[i][j] == words[k]，但 不是 words中的最后一个字符,对当前这个记录进行特殊标记，
        // 表示该元素已经访问过，避免后面元素搜索上左下右时再次访问
        board[i][j]='#';

        //探索 当前元素的 上左下右 四个方向，寻找 words[k+1]这个字符
        boolean res=dfs(board,words,i-1,j,k+1)
        || dfs(board,words,i,j-1,k+1)
        || dfs(board,words,i+1,j,k+1)
        || dfs(board,words,i,j+1,k+1);

        //再回退到当前元素
        board[i][j]=words[k];

        return res;
    }


}
